package com.xiaoming;

import java.util.Arrays;

public class 插入排序 {

    public static void main(String[] args) {
        int[] arr = new int[]{33, 23, 42, 11, 65, 22};
        System.out.println("排序前：" + Arrays.toString(arr));
        arrSort(arr);
        System.out.println("排序前：" + Arrays.toString(arr));
    }

    private static void arrSort(int[] arr) {
        int length = arr.length;
        for (int i = 1; i < length; i++) {//默认第一个已经排好序、所以从第二个开始循环
            int key = arr[i];//当前值
            int index = i - 1;//取前一个值的索引
            while (index >= 0 && arr[index] > key) {//从前一个值的索引开始往前进行循环，遇到比当前大的值就把位置往后移
                arr[index + 1] = arr[index];
                index--;
            }
            arr[index + 1] = key;//最后把当前值塞到剩余位置
        }
    }
}
